package _0_4_买卖股票

/*
*
原题链接:
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/

123. 买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。

	随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

	注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
	因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：
输入：prices = [1]
输出：0

思路:
一. dp数组含
  - 一天一共就有五个状态
    0.没有操作 (其实我们也可以不设置这个状态)
    1.第一次买入,持有股票
    2.第一次卖出,不持有股票
    3.第二次买入,持有股票
    4.第二次卖出不持有股票

dp[i][j] i表示第i天, j为[0-4]五个状态, dp[i][j]表示第i天状态j所剩最大现金.
例如dp[i][1], 表示第i天, 第一次持有股票状态, 所持有的现金数

二. 递推公式
第一次持有股票, 达到dp[i][1]状态, 有两个具体操作:
  - 操作一: 第i天第一次买入股票了, 那么dp[i][1] = dp[i-1][0] - prices[i]
  - 操作二: 第i天没有操作, i-1天已经进行了第一次买入, 即dp[i][1] = dp[i-1][1]

那么dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])

同理, 第一次不持有股票, dp[i][2]也有两个操作
  - 操作一: 第i天卖出股票了, 那么dp[i][2] = dp[i-1][1] + prices[i]
  - 操作二: 第i天没有操作, i-1天就将第一次持有的股票卖出了, 即: dp[i][2] = dp[i-1][2]

那么dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2])

同理可推剩下状态部分:
dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])
dp[i][4] = max(dp[i-1][4], dp[i-1][3] - prices[i])

二. 递推公式
第一次持有股票, 达到dp[i][1]状态, 有两个具体操作:

	操作一: 第i天第一次买入股票了, 那么dp[i][1] = dp[i-1][0] - prices[i]
	操作二: 第i天没有操作, i-1天就已经进行了第一次买入, 即dp[i][1] = dp[i-1][1]

那么dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])

同理, 第二次不持有股票, dp[i][2]也有两个操作

	操作1: 第i天卖出股票了, 那么dp[i][2] = dp[i-1][1] + prices[i]
	操作2: 第i天没有操作, i-1天就将第一次持有的股票卖出了, 即: dp[i][2] = dp[i-1][2]

那么dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2])

三. 初始化
第0天没有操作, 那么dp[0][0] = 0
第0天做第一次买入的操作, dp[0][1] = -prices[0]
第0天做第一次卖出的操作, 可理解为买了又卖出, 所以dp[0][2] = 0
同理,第0天第二次买入的操作, 初始化为: dp[0][3] = -prices[0]
第0天第二次卖出初始化dp[0][4] = 0

四. 确定遍历顺序
第i天状态都是从i-1推导的, 那么需要从前向后遍历

五. 打印dp数组
*/
func maxProfit123(prices []int) int {

	n := len(prices)

	dp := make([][]int, n) //声明二维数组, 每个i位置有五个状态
	for i := 0; i < n; i++ {
		dp[i] = make([]int, 5)
	}

	//将第0天的五种状态分别初始化
	dp[0][0] = 0
	dp[0][1] = -prices[0]
	dp[0][2] = 0
	dp[0][3] = -prices[0]
	dp[0][4] = 0

	//递推公式, 填充dp数组
	for i := 1; i < n; i++ {
		dp[i][0] = dp[i-1][0]
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]) //第1次买卖, 持有股票状态   可能是昨天就持有股票, 可能是昨天不持有股票,今天刚刚买入
		dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i]) //第1次买卖, 不持有股票状态  可能是昨天就不持有股票, 可能是昨天今天持有股票,今天刚刚卖出
		dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i]) //第2次买卖, 持有股票状态	  可能是昨天就持有股票, 可能是昨天不持有股票,今天刚刚买入
		dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i]) //第2次买卖, 不持有股票状态  可能是昨天就不持有股票, 可能是昨天今天持有股票,今天刚刚卖出
	}

	return dp[len(prices)-1][4] //返回第i天,状态4所持有的现金数
}
